package com.data2.java.show.datastructure;

/**
 * @author leewow
 * @description
 * @date 2020/9/16 下午10:01
 *
 * 1、定义
 *
 * 堆 - 堆是一种非线性结构，利用完全二叉树的结构来维护的一维数组
 *      逻辑结构：完全二叉树
 *      物理结构：一维数组
 *
 * 2、分类
 *
 *  大顶堆 - 每个结点的值都大于或等于其左右孩子结点的值 arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 *  小顶堆 - 每个结点的值都小于或等于其左右孩子结点的值 arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 *
 *  （堆的这种特性非常的有用，堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素）
 *
 * 3、堆和普通树的区别
 *
 * 普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外的内存。
 * 堆仅仅使用数组，且不使用指针（可以使用普通树来模拟堆，但空间浪费比较大，不太建议这么做）
 *
 * 平衡：
 * 二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(nlog2n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，
 *
 * 搜索：
 * 在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作
 *
 *
 * 4、排序 - 数组实现
 *
 * 思想：
 *      将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。
 *      然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。
 *
 * 步骤：
 *      第一步：先n个元素的无序序列，构建成大顶堆
 *      第二步：将根节点与最后一个元素交换位置，（将最大元素"沉"到数组末端）
 *      第三步：交换过后可能不再满足大顶堆的条件，所以需要将剩下的n-1个元素重新构建成大顶堆
 *      第四步：重复第二步、第三步直到整个数组排序完成
 *
 * 升序----使用大顶堆
 * 降序----使用小顶堆
 *
 * 5、排序 - PriorityQueue  - 默认小顶堆
 *
 *  降序----使用大顶堆
 *  升序----使用小顶堆
 *
 */
public class Heap {
}
